1
效率之尺:為什麼大 O 記法是程式員的通用語?
AI028Lesson 2
00:00

時間複雜度(Time Complexity) 並非用來衡量演算法運行的絕對秒數,而是一種描述演算法執行時間隨問題規模 $n$ 增長而增長的數學函數。其基礎建立於「演算法分析是一種獨立於實作的演算法度量方法」這一核心原則之上。

規模 $n$時間 $T(n)$$O(n^2)$$O(n)$$O(\log n)$$O(1)$

為什麼它是通用語?

  • 量化演進:大 O 記法忽略低階項與常數,僅聚焦於數量級(Order of Magnitude)
  • 度量的確定性:程式員通常以最壞情況(Worst Case) 作為基準,為效能提供下限保障。
  • 跨環境決策:無論是在超級電腦還是嵌入式晶片中,從 $O(n^2)$ 優化至 $O(n \log n)$ 所帶來的效益都是本質性的。
計數法(Counting)
計算兩個字串中每個字元出現的次數。若字元計數列表相同,則兩個字串必為異序詞。此方法實現了 計數法:$O(n)$ 的高效性。